package alo.p3.work;

import alo.p3.ListNode;
//把两个有序表合并成一个有序表
public class MergeList {
    ListNode MergeList(ListNode l1, ListNode l2){
        ListNode result=null;
        if (l1==null) return l2;
        if(l2==null) return l1;
        if (l1.getData()<l2.getData()){
            result=l1;
            result.setNext(MergeList(l1.getNext(),l2));
        }else {
            result=l2;
            result.setNext(MergeList(l1,l2.getNext()));

        }
        return result;
    }
    //不创建新的结点
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.getData() < l2.getData()) {
            l1.setNext(mergeTwoLists(l1.getNext(),l2));
            return l1;
        } else {
            l2.setNext(mergeTwoLists(l1,l2.getNext()));
            return l2;
        }

    }




    //使用迭代的方法
    public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);
        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.getData() <= l2.getData()) {
                prev.setNext(l1);
                l1 = l1.getNext();
            } else {
                prev.setNext(l2);
                l2 = l2.getNext();
            }
            prev = prev.getNext();
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.setNext(l1 == null ? l2 : l1);

        return prehead.getNext();
    }
}
